\documentclass[UTF8]{ctexart}
\usepackage{listings} 
\usepackage{xcolor}
\usepackage{fancyhdr}%设置页脚页眉需要的包
\pagestyle{fancy}
\usepackage{graphicx}
\usepackage{cite}
\usepackage{booktabs}
\usepackage{tikz}
\documentclass{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{float}
\usepackage{amsthm}
\usepackage{xeCJK}
\usepackage{graphicx}
\usepackage{fullpage}
\usepackage{gnuplottex}
\usepackage{geometry}
\usepackage{enumitem}
\usepackage{verbatimbox}
\usepackage{amsfonts,amssymb} 
\usepackage[ruled,linesnumbered]{algorithm2e}
\usepackage[colorlinks,linkcolor=blue,citecolor=blue]{hyperref}
\usepackage{cite}
\CTEXsetup[format={\Large\bfseries}]{section}
\newtheorem{example}{例}             % 整体编号
\newtheorem{theorem}{定理}[section]  % 按 section 编号
\newtheorem{definition}{定义}
\newtheorem{axiom}{公理}
\newtheorem{property}{性质}
\newtheorem{proposition}{命题}
\newtheorem{lemma}{引理}
\newtheorem{corollary}{推论}
\newtheorem{remark}{注解}
\newtheorem{condition}{条件}
\newtheorem{conclusion}{结论}
\newtheorem{assumption}{假设}
\newcommand{\enabstractname}{Abstract}
\newenvironment{enabstract}{%
    \par\small
    \noindent\mbox{}\hfill{\bfseries \enabstractname}\hfill\mbox{}\par
    \vskip 2.5ex}{\par\vskip 2.5ex}
\usetikzlibrary{positioning, shapes.geometric}
\lstset{
  language=C++,
  frame=shadowbox,
  rulesepcolor=\color{red!20!green!20!blue!20},
  keywordstyle=\color{blue!90}\bfseries,
  commentstyle=\color{red!10!green!70}\textit,
  showstringspaces=false,
  numbers=left,
  numberstyle=\tiny,
  stringstyle=\ttfamily,
  breaklines=true,
  extendedchars=false,
  texcl=true}

\title{Theoretical Assignment IV}

\author{韩骐骏 \\ (数学科学学院)信息与计算科学3200103585}

\begin{document}

\maketitle

\section{Problem 4.4.1 I}
\subsection{Solution}
Continuously divide by $2$ and take the remainder, we have $477=2*238+1$, $......$(ignore in the process of written calculation), $3=2*1+1$, $1=2*0+1$. Arrange the remainder in order to get $$477_{10}=111011101_{2}=1.11011101_{2}*2^8$$

\section{Problem 4.4.1 II}
\subsection{Solution}
Continue to multiply by $2$ and take the integral part, we have $2*0.6=1+0.2$, $2*0.2=0+0.4$, $......$(ignore in the process of written calculation), it can be found that $0.6$ is an infinite circular decimal under binary system, like $$0.6_{10}=0.1001100110011001..._{2}=1.001100110011001..._{2}*2^{-1}$$.

\section{Problem 4.4.1 III}
\subsection{Solution}
Obviously $$x_R-x=\beta^{e-(p-1)}=\beta*\beta^{(e-1)-(p-1)}=\beta(x-x_L)$$

\section{Problem 4.4.1 IV}
\subsection{Solution}
IEEE 754 single precision significant digits are $24$, thus$$x_L=1.0011001100110011001_{2}*2^{-1}$$ $$x_R=1.0011001100110011010_{2}*2^{-1}$$ Obviously $x_R-x<x-x_L$, thus $$fl(0.6)=x_R=1.0011001100110011010_{2}*2^{-1}$$  The relative roundoff error calculated by calculator is $$\frac{|x_R-x|}{|x|}=\frac{0.00000038147}{0.60000038147}\approx 0.000000635783$$

\section{Problem 4.4.1 V}
\subsection{Solution}
At this time, it will be judged whether to round to $x_L$ or $x_R$ according to the positive and negative, so there may be a case where $x$ is infinitely close to $x_L$ but rounded to $x_R$. Thus $\epsilon_u=\epsilon_M$.

\section{Problem 4.4.1 VI}
\subsection{Solution}
It can be computed that $1-\cos(\frac{1}{4})=0.0000011111110101_2$, thus $6$ bits of precision are lost in the subtraction.

\section{Problem 4.4.1 VII}
\subsection{Solution}
One way is by Taylor expansion, we can get $1-\cos x=\frac{x^2}{2!}-\frac{x^4}{4!}+\frac{x^6}{6!}-...$, and we only take the $\frac{x^2}{2!}$ part.\\The second way is directly compute $1-\cos x=2\sin^2\frac{x}{2}$.

\section{Problem 4.4.1 VIII}
\subsection{Solution}
It can be calculated in turn that:\\
When $f(x)=(x-1)^{\alpha}$,  $$C_f(x)=\frac{|x\alpha(x-1)^{\alpha-1}|}{|(x-1)^{\alpha}|}=|\frac{\alpha x}{x-1}|$$Which is large when $x\rightarrow 1$.\\
When $f(x)=\ln x$,  $$C_f(x)=\frac{|x\frac{1}{x}|}{|\ln x|}=|\frac{1}{\ln x}|$$Which is large when $x\rightarrow 1$.\\
When $f(x)=e^x$,  $$C_f(x)=\frac{|xe^x|}{|e^x|}=|x|$$Which is large when $x\rightarrow \infty$.\\
When $f(x)=\arccos x$,  $$C_f(x)=\frac{|x\frac{1}{\sqrt{1-x^2}}|}{|\arccos x|}=|\frac{x}{\sqrt{1-x^2}\arccos x}|$$Which is large when $x\rightarrow 1$.\\

\section{Problem 4.4.1 IX}
\subsection{Question I}
$$C_f(x)=|\frac{xe^{-x}}{1-e^{-x}}|=|\frac{x}{e^x-1}|\leq |\frac{x}{x}|=1,\forall x\in [0,1]$$

\subsection{Question II}
$$f_A(x)=(1+\delta_1)-(1+\delta_1)(1+\delta_2)e^{-x}\leq (1-e^{-x})\varphi(x)$$where $\varphi(x)=\frac{1}{1-e^{-x}}$, thus $$cond_A(x)\leq \frac{\varphi(x)}{cond_f(x)}=\frac{e^x}{x}\leq e$$

\subsection{Question III}
\begin{figure}[H]
    \centering
    \includegraphics[width=13cm]{pic1}
    \caption{V.(e)}
    \label{fig:galaxy}
\end{figure}
The left figure is $cond_A(x)$, and the right figure is $cond_f(x)$. From the figure, we can see that for $f$, theoretically, the disturbance near $0$ is not large. But from the actual calculation, when $x$ tends to $0$, the instability will be significantly improved.

\section{Problem 4.4.1 X}
\subsection{Solution}
$$cond_f(r)=\sum_{i=0}^{n-1}|\frac{a_i}{r}\frac{\partial r}{\partial a_i}|=\sum_{i=0}^{n-1}\frac{|a_ir^{i-1}|}{|nr^{n-1}+a_{n-1}(n-1)r^{n-2}+\cdots+a_1|}$$It can be seen that the number of conditions near the extreme point of q will tend to be very large, leading to the increase of instability. For the Wilkinson example, it can be found that the condition numbers are very large by substituting their roots, and there is a positive correlation with the order of the polynomial, which shows that the instability of finding roots will increase rapidly with the increase of the order of the polynomial.

\section{Problem 4.4.1 XI}
\subsection{Solution}
Consider FPN system with $\beta=2,p=2$, and $x=0.5_{10},y=0.6_{10}$.
Then  $1.2_{10}=\frac{y}{x}\approx 1.0011001100110011$, it will be revised to $1.010_2=1.25_{10}$, thus we have $\frac{1.25-1.2}{1.2}\approx0.0417>\frac{1}{2}2^{1-2}=\epsilon_u$, this creates a contradiction!

\section{Problem 4.4.1 XII}
\subsection{Solution}
Under IEEE 754 single precision FPN system, we have $128_{10}=1.000...0_{2}*2^7$, thus $2^{1-24+7}=2^{-16}\approx 0.000015258789>10^{-6}$, so we can't compute with absolute accuracy $<10^{-6}$.

\section{Problem 4.4.1 XIII}
\subsection{Solution}
Consider $x_{i+1}-x_i=\delta$, we have the coefficient matrix
\begin{equation}
	\begin{bmatrix}
		(x_{i+1}-x_i)^2 & (x_{i+1}-x_i)^3 \\
		2(x_{i+1}-x_i) & 3(x_{i+1}-x_i)^2 \\
	\end{bmatrix}_{2\times 2}
\end{equation}
That is
\begin{equation}
	\begin{bmatrix}
		\delta^2 & \delta^3 \\
		2\delta & 3\delta^2 \\
	\end{bmatrix}_{2\times 2}
\end{equation}
We can compute that $$||A||_1*||A^{-1}||_1=(2\delta+\frac{1}{\delta^3})(\frac{3}{\delta^2}+\frac{2}{\delta^2})>\frac{1}{\delta}\rightarrow\infty,\delta\rightarrow\infty$$It can be seen that if two sampling points are very close, the condition number of the coefficient matrix must be very large, that is, the coefficient matrix is ill conditioned, so the instability of the fitting is bound to increase.

\end{document}
